package com.fr.lintcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

public class Q1029 {
    /**
     * @param n:
     *            a integer
     * @param flights:
     *            a 2D array
     * @param src:
     *            a integer
     * @param dst:
     *            a integer
     * @param K:
     *            a integer
     * @return: return a integer
     */
    int min = Integer.MAX_VALUE;

    public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
        // write your code here
        if (flights == null || flights.length == 0 || flights[0].length == 0 || src >= flights.length
            || dst >= flights.length) {
            return -1;
        }
        int count = -1;
        int sum = 0;
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for (int[] flight : flights) {
            Map<Integer, Integer> tmp = map.get(flight[0]);
            if (tmp == null) {
                tmp = new HashMap<>();
                map.put(flight[0], tmp);
            }
            tmp.put(flight[1], flight[2]);
        }
        Set<Integer> filter = new HashSet<>();
        search(count, sum, src, dst, filter, map, K, n);
        if (min == Integer.MAX_VALUE) {
            min = -1;
        }
        return min;
    }

    private void search(int count, int sum, int src, int dst, Set<Integer> filter,
        Map<Integer, Map<Integer, Integer>> map, int k, int n) {
        if (count > k || (min != Integer.MAX_VALUE && sum > min)) {
            return;
        }
        if (src == dst) {
            if (sum < min) {
                min = sum;
            }
            return;
        }
        Map<Integer, Integer> flights = map.get(src);
        for (Map.Entry<Integer, Integer> entry : flights.entrySet()) {
            if (!filter.contains(entry.getKey())) {
                filter.add(entry.getKey());
                sum += entry.getValue();
                search(count + 1, sum, entry.getKey(), dst, filter, map, k, n);
                filter.remove(entry.getKey());
                sum -= entry.getValue();
            }
        }
    }

    @Test
    public void testA() {
        int[][] a = {{0, 1, 100}, {1, 2, 100}, {0, 2, 500}};
        System.out.println(findCheapestPrice(3, a, 0, 2, 1));
    }

}
